package com.LeeCode;

/**
 * 有序数组中的单一元素
 */

public class Code540 {
    public static void main(String[] args) {
        int[] nums = {1,1,3};
        System.out.println(new Code540().singleNonDuplicate1(nums));
    }

    public int singleNonDuplicate(int[] nums) {
        int index = 0;
        while (index < nums.length) {
            if (index == nums.length - 1 || nums[index] != nums[index + 1]) {
                break;
            }
            index += 2;
        }
        return nums[index];
    }

    public int singleNonDuplicate1(int[] nums) {
        int left = -1, right = nums.length - 1;
        while (left + 1 < right) {
            int mid = (left + right) >> 1;
            if (check(nums, mid))
                right = mid;
            else
                left = mid;
        }
        return nums[right];
    }

    private boolean check(int[] nums, int mid) {
        if ((mid & 1) == 0) {
            return nums[mid] != nums[mid + 1];
        } else {
            return nums[mid] != nums[mid - 1];
        }
    }
}

